package com.heima.datastructure.btree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * <h2><strong>B树</strong></h2>
 * <h3>B树历史</h3>
 * <ul>
 *     <li>如果100w条数据用avl树来存储，树高为28 - 29</li>
 *     <li>如果100w条数据用红黑树来存储，树高为39 - 40</li>
 *     <li>如果100w条数据用B树来存储，树高为2 - 6</li>
 *     <li>由此可见B树很适合用来做磁盘存储，树高低，那么磁盘的I/O次数更少</li>
 * </ul>
 * <h3>B树的特性</h3>
 * <ol>
 *     <li>度：degree 指树中节点的孩子数</li>
 *     <li>阶：order 指所有节点孩子数的最大值</li>
 *     <li>每个节点最多有m个孩子，其中m称为B树的阶</li>
 *     <li>除了根节点和叶子节点外，其他每个节点至少有ceil(m / 2)个孩子</li>
 *     <li>除了根节点外，其他每个节点至少有ceil(m / 2) - 1个key</li>
 *     <li>若根节点不是叶子节点，则至少有两个孩子</li>
 *     <li>所有叶子节点都在同一层</li>
 *     <li>每个非叶子节点都由n个关键字和n + 1个指针（孩子）组成，其中ceil(m / 2) <= n + 1 <= m</li>
 *     <li>关键字按非降序排列，即节点中的第i个关键字大于等于i - 1个关键字</li>
 *     <li>节点有n + 1个子树，其中最左边和最右边对应小于节点中第一个关键字和大于节点中最后一个关键字，其余子树就是相邻关键字之间的空隙</li>
 * </ol>
 * <ol>
 *         <li><strong>多路性：</strong>B树的每个节点可以有多个子节点，而不仅仅是两个，这使得B树可以存储更多的键值，从而减少树的高度，提升查找效率</li>
 *         <li><strong>有序性：</strong>每个节点中的键值是有序的，节点中的键值将子节点分隔开，使得查找操作可以通过比较键值来快速定位</li>
 *         <li><strong>平衡性：</strong>B树是平衡的，所有的叶子节点都在同一层次上，这保证了在最坏情况下的查找时间是对数级别的</li>
 *         <li><strong>动态性：</strong>B树可以根据需要动态的增长或缩小，支持高效的插入和删除操作，而不会破坏树的平衡性</li>
 *         <li><strong>适合做磁盘存储：</strong>B树的设计考虑了磁盘存储的特性，能够有效地减少磁盘I/O操作。</li>
 *         <li><strong>所有操作的时间复杂度：</strong>B树的查找、插入、删除操作的时间复杂度均为O(log n)</li>
 * </ol>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/17 12:53
 */
public class Btree<K extends Comparable<K>, V> {
    private BNode<K, V> root; // 根节点
    private final int minDegree; // 最小度数，大于等于2
    private final int MIN_KEY_NUMBER; // 最小关键字个数，大于等于1
    private final int MAX_KEY_NUMBER; // 最大关键字个数，大于等于2 * minDegree - 1

    /**
     * 无参构造器初始化，默认最小度数是2
     */
    public Btree() {
        this(2); // 默认最小度数为2
    }

    /**
     * 有参构造方法初始化
     *
     * @param minDegree 最小度数
     */
    public Btree(int minDegree) {
        this.minDegree = minDegree;
        root = new BNode<>(minDegree); // 创建节点时默认就是叶子节点
        MIN_KEY_NUMBER = minDegree - 1;
        MAX_KEY_NUMBER = minDegree * 2 - 1;
    }

    /**
     * 节点类，当前包可以用这个类以及这个类的方法
     *
     * @param <K> key的数据类型，要实现Comparable接口
     * @param <V> value的数据类型，存值
     */
    static class BNode<K extends Comparable<K>, V> { // 内部节点类，与外部类相互独立，所以用static，不加public修饰，范围是当前包，内部变量也不用加public修饰
        List<K> keys; // 关键字的集合
        List<V> values; // 存储的值的集合
        List<BNode<K, V>> children; // 孩子节点的集合
        boolean isLeaf; // 是否为叶子节点，boolean类型成员变量默认初始化是false
        int minDegree; // 最小度数，大于2

        /**
         * 构造方法
         *
         * @param minDegree 最小度数
         */
        BNode(int minDegree) {
            this.minDegree = minDegree;
            this.keys = new ArrayList<>(minDegree * 2 - 1); // 最多关键字个数是2 * minDegree - 1
            this.values = new ArrayList<>(minDegree * 2 - 1); // 最多值个数是2 * minDegree - 1
            this.children = new ArrayList<>(minDegree * 2); // 因为最多度数 / 2是最小度数，所以最多度数是2 * minDegree
            this.isLeaf = true; // 设置添加一个节点默认设置为叶子节点，put方法会改的
        }

        @Override
        public String toString() {
            return keys.toString();
        }

        // 多路查找

        /**
         * 查找key对应的节点
         *
         * @param key key
         * @return 节点
         */
        BNode<K, V> get(K key) {
            int i = 0;
            while (i < keys.size()) {
                if (key.compareTo(keys.get(i)) == 0) {
                    return this;
                } else if (key.compareTo(keys.get(i)) < 0) {
                    break;
                } else {
                    i++;
                }
            }
            if (isLeaf) {
                return null;
            }
            return children.get(i).get(key);
        }

        // 插入指定键值对

        /**
         * 向键集合中插入指定键值对
         * 此方法会在键集合中的指定位置插入给定的键值
         * 插入后，该键后面的所有键都会向后移动一个位置
         *
         * @param key   要插入的键
         * @param value 要插入的值
         * @param index 插入的位置
         */
        void insertKey(K key, V value, int index) {
            keys.add(index, key); // 带index的add方法，当index是size（）的时候也是合法的，表示add(e)
            values.add(index, value);
        }

        // 插入指定孩子

        /**
         * 向孩子集合中插入指定孩子节点
         *
         * @param child 要插入的孩子节点
         * @param index 插入孩子的索引
         */
        void insertChild(BNode<K, V> child, int index) {
            if (children.isEmpty()) {
                isLeaf = false;
            }
            children.add(index, child);
        }

        /**
         * 删除指定索引的key
         *
         * @param index 指定的索引
         * @return 删除的key
         */
        @SuppressWarnings("all")
        K removeKey(int index) {
            return keys.remove(index);
        }

        /**
         * 删除节点最左key
         *
         * @return 返回删除的最左边的key
         */
        K removeLeftMostKey() {
            return keys.remove(0);
        }

        /**
         * 删除最右边的key
         *
         * @return 返回删除的最右边的key
         */
        K removeRightMostKey() {
            return keys.remove(keys.size() - 1);
        }

        /**
         * 删除指定索引的value
         *
         * @param index 要删除的索引
         * @return 返回被删除的值
         */
        V removeValue(int index) {
            return values.remove(index);
        }

        /**
         * 删除最左边的value
         *
         * @return 返回被删除的最左边的值
         */
        V removeLeftMostValue() {
            return values.remove(0);
        }

        /**
         * 删除最右边的value
         *
         * @return 返回被删除的最右边的值
         */
        V removeRightMostValue() {
            return values.remove(values.size() - 1);
        }

        /**
         * 删除指定索引的child
         *
         * @param index 要删除的索引
         * @return 返回被删除的孩子节点
         */
        @SuppressWarnings("all")
        BNode<K, V> removeChild(int index) {
            return children.remove(index);
        }

        /**
         * 删除最左边的child
         *
         * @return 返回被删除的最左边的孩子节点
         */
        BNode<K, V> removeLeftMostChild() {
            return children.remove(0);
        }

        /**
         * 删除最右边的child
         *
         * @return 返回被删除的最右边的孩子节点
         */
        BNode<K, V> removeRightMostChild() {
            return children.remove(children.size() - 1);
        }

        /**
         * 获取当前节点指定索引的孩子节点的左兄弟节点
         *
         * @param index 指定孩子的索引
         * @return 左兄弟节点，如果没有，返回null
         */
        BNode<K, V> childLeftSibling(int index) {
            return index > 0 ? children.get(index - 1) : null;
        }

        /**
         * 获取当前节点指定索引的孩子节点的右兄弟节点
         *
         * @param index 指定孩子的索引
         * @return 右兄弟节点，如果没有，返回null
         */
        BNode<K, V> childRightSibling(int index) {
            return index < children.size() - 1 ? children.get(index + 1) : null;
        }

        /**
         * 将当前节点的所有内容移动到目标节点中
         *
         * @param target 目标节点
         */
        void moveToTarget(BNode<K, V> target) {
            target.keys.addAll(this.keys);
            target.values.addAll(this.values);
            target.children.addAll(this.children);
        }
    }

    /**
     * 获取指定键的值
     *
     * @param key 要查找的键
     * @return 找到的值，如果没有找到，返回null
     */
    public V get(K key) {
        return get(root, key);
    }

    /**
     * 递归实现查找
     *
     * @param root 当前树的根节点
     * @param key  带查找的键
     * @return 返回值，如果没有找到，返回null
     */
    private V get(BNode<K, V> root, K key) {
        int index = 0;
        while (index < root.keys.size()) {
            if (key.compareTo(root.keys.get(index)) == 0) {
                return root.values.get(index);
            } else if (key.compareTo(root.keys.get(index)) < 0) {
                break;
            } else {
                index++;
            }
        }
        if (root.isLeaf) {
            return null;
        } else {
            return get(root.children.get(index), key);
        }
    }

    /**
     * set操作
     *
     * @param key   要修改的键
     * @param value 修改成多少
     * @throws IllegalArgumentException 如果key不存在，抛出异常
     */
    public void set(K key, V value) {
        if (!contains(key)) {
            throw new IllegalArgumentException("key not found");
        }
        put(key, value);
    }

    /**
     * 判断是否包含指定键
     *
     * @param key 要查找的键
     * @return 包含指定键返回true，否则返回false
     */
    public boolean contains(K key) {
        return root.get(key) != null;
    }

    /**
     * put方法，实现往B树中插入键值，并调整插入后的B树
     *
     * @param key   待插入的键
     * @param value 待插入的值
     */
    public void put(K key, V value) {
        put(root, key, value, null, 0);
    }

    /**
     * put方法递归实现
     *
     * @param root   当前树的根节点
     * @param key    关键字
     * @param value  值
     * @param parent 当前树根节点的父节点
     * @param index  当前树位于当前树根节点的父节点的孩子的索引
     */
    private void put(BNode<K, V> root, K key, V value, BNode<K, V> parent, int index) {
        int i = 0;
        // 找到key的位置
        while (i < root.keys.size()) {
            if (key.compareTo(root.keys.get(i)) == 0) { // 找到了，则修改然后退出
                root.values.set(i, value);
                return;
            } else if (key.compareTo(root.keys.get(i)) < 0) { // 遍历到的key比要插入的key要大，第一次出现就要退出循环，确保正确插入位置
                break;
            } else { // 当前的key比要插入的key要小，则往后找，直到出现第一个比key大的或者退出循环
                i++;
            }
        }
        // 如果是叶子节点，则直接插入
        if (root.isLeaf) {
            root.insertKey(key, value, i);
        }
        // 如果不是叶子节点，则递归调用在子树中插入
        else {
            put(root.children.get(i), key, value, root, i);
        }
        if (root.keys.size() == MAX_KEY_NUMBER) { // 能走到这可能是叶子节点，也可能是非叶子节点(孩子分裂的时候让父节点满了)
            // 插入后，如果关键字个数大于最大的允许个数，则需要分裂，最大的就是2 * minDegree - 1，最小的是minDegree - 1
            // 1、创建一个right节点，把当前节点右半部分，也就是minDegree ~ 2 * minDegree - 1移动到当前节点
            // 2、把当前节点索引为minDegree - 1的key，也就是正中间的key，移动到当前节点的父节点中
            // 3、当前节点剩余的作为其父节点第index个子孩子，right节点作为父节点第index + 1个子孩子插入，index为当前节点原本位于父节点子孩子的索引
            split(root, parent, index);
        }
    }

    /**
     * split方法，实现分裂节点
     *
     * @param node   node，要分裂的节点
     * @param parent 分裂节点的父节点
     * @param index  当前分裂节点位于父节点的索引
     */
    private void split(BNode<K, V> node, BNode<K, V> parent, int index) {
        // 如果分裂的节点是根节点
        if (parent == null) {
            // 父节点创建出来
            parent = new BNode<>(minDegree);
            // 建立关系
            parent.insertChild(node, 0);
            // 修改root
            root = parent;
        }
        // 1、创建一个right节点，把node的右半部分，从minDegree ~ 2 * minDegree - 1移动到right节点。node要分裂，说明肯定是满的，所以node的keys长度是奇数
        BNode<K, V> right = new BNode<>(minDegree);
        right.isLeaf = node.isLeaf;
        right.keys = new ArrayList<>(node.keys.subList(minDegree, MAX_KEY_NUMBER)); // 不要直接引用
        right.values = new ArrayList<>(node.values.subList(minDegree, MAX_KEY_NUMBER)); // 不要直接引用
        // 如果不是叶子节点，则把node的右半孩子minDegree ~ MAX_KEY_DEGREE + 1或者minDegree ~ 2 * minDegree
        if (!node.isLeaf) {
            right.children = new ArrayList<>(node.children.subList(minDegree, MAX_KEY_NUMBER + 1));
        }
        // 2、然后把node索引为minDegree - 1的key，也就是正中间的key，插入到parent中，作为parent的第index个key
        parent.insertKey(node.keys.get(minDegree - 1), node.values.get(minDegree - 1), index);
        // 3、node剩余的作为其父节点第index个子孩子，right节点作为父节点第index + 1个子孩子插入，index为node原本位于父节点子孩子的索引
        parent.insertChild(right, index + 1);
        // 清空指定范围的键值对
        node.keys.subList(minDegree - 1, MAX_KEY_NUMBER).clear();
        node.values.subList(minDegree - 1, MAX_KEY_NUMBER).clear();
        // 要分裂的节点不是叶子节点，则把要分出去的孩子清空
        if (!node.isLeaf) {
            node.children.subList(minDegree, MAX_KEY_NUMBER + 1).clear();
        }
    }

    /**
     * 删除指定键对应的键值，并且平衡树返回值
     *
     * @param key 要删除的键
     * @return 返回要删除的键对应的值
     */
    public V remove(K key) {
        return remove(root, key, null, 0);
    }

    /**
     * 实现的remove方法，递归实现，逻辑主要在于删除
     * @param root 当前树根节点
     * @param key 要删除节点的key
     * @param parent 当前树根节点的父节点
     * @param index 当前树位于父节点众多子树中的索引
     * @return 返回要删除的键对应的值，如果没找到，则返回null
     */
    private V remove(BNode<K, V> root, K key, BNode<K, V> parent, int index) {
        // 找出要删除的键值
        int i = 0; // 记录要删除的key的位于当前根节点的keys的索引
        boolean found = false; // 是否在当前根节点的keys中找到key，默认为false，没找到
        V value = null; // 要删除的key对应的值
        while (i < root.keys.size()) {
            // 找到了，退出循环
            if (key.compareTo(root.keys.get(i)) == 0) {
                found = true;
                break;
            }
            // 遍历到的key比要插入的key要大，第一次出现就要退出循环，确保正确插入位置
            else if (key.compareTo(root.keys.get(i)) < 0) {
                break;
            }
            // 当前的key比要插入的key要小，则往后找，直到出现第一个比key大的或者退出循环
            i++;
        }
        // 当前节点如果是叶子节点
        if (root.isLeaf) {
            // 在当前节点找到了删除节点的key的索引
            if (found) {
                root.removeKey(i);
                value = root.removeValue(i);
            }
            // 在当前节点没找到删除节点的key的索引
            else {
                return value; // 叶子节点都没找到该节点，说明肯定没有该节点，返回null
            }
        }
        // 当前节点如果不是叶子节点
        else {
            // 在当前节点找到了删除节点的key的索引
            if (found) {
                // 李代桃僵，将后继节点的键值赋值给当前根节点，然后递归删除后继节点（原后继节点的键值是没有变化的）
                // 1、找到后继节点
                BNode<K, V> successor = root.children.get(i + 1); // 当前情况是找到了key，所以应该到i + 1个子树去找后继节点
                while (!successor.isLeaf) { // 叶子节点都在同一层
                    successor = successor.children.get(0);
                }
                K sKey = successor.keys.get(0);
                V sValue = successor.values.get(0);
                // 2、后继节点的键值代替当前根节点的键值
                value = root.values.get(i);
                root.keys.set(i, sKey);
                root.values.set(i, sValue);
                // 3、递归删除原后继节点（从当前根节点的子树中删）
                remove(root.children.get(i + 1), sKey, root, i + 1);
            }
            // 在当前节点没找到删除节点的key的索引
            else {
                value = remove(root.children.get(i), key, root, i); // i对应的孩子节点作为根节点的子树递归删除
            }
        }
        // 删除后，如果当前节点的keys数量小于MIN_KEY_NUMBER，则需要平衡调整
        if (root.keys.size() < MIN_KEY_NUMBER) { // 整棵树的根节点也会进来这个判断，只要如果有拿走了键值，只要根节点不为空直接返回
            balance(root, parent, index); // 不止一次的平衡调整，虽然删除节点最后会转移到叶子节点删除，但是叶子节点删除时会索取父节点的键值，当父节点被索取后也不平衡的时候就需要调整了
        }
        // 返回删除的值
        return value;
    }

    /**
     * 平衡调整，如果当前节点的keys数量小于MIN_KEY_NUMBER，则需要调整，调整分为左旋和右旋，合并
     * @param node 当前要处理的子树的根节点
     * @param parent 当前子树根节点节点的父节点
     * @param index 当前节点位于父节点的子树中的索引
     */
    private void balance(BNode<K, V> node, BNode<K, V> parent, int index) {
        // 当前要处理节点是根节点，特殊处理
        if (node == root) {
            // 如果根节点是空的，则把根节点的子树作为根节点，就是根节点的键值被拿走了，变为空，但是还有子树
            if (root.keys.isEmpty() && root.children.get(0) != null){
                root = root.children.get(0); // 根节点的第一个子树作为根节点，因为左右孩子都不富余都是往左合并，合并后肯定只有一个子树，所以直接把子树作为根节点（根节点要为空，则拿走前是1个键值，那么只有两个子树，所以合并后就只有第一个子树了）
            }
            // 根节点也会进来处理平衡，但是根节点比较特殊，只要不为空，则不做任何处理返回
            return;
        }
        BNode<K, V> leftSibling = parent.childLeftSibling(index);
        BNode<K, V> rightSibling = parent.childRightSibling(index);
        // 当前要处理的节点的左兄弟富余，则来一次右旋
        if (leftSibling != null && leftSibling.keys.size() > MIN_KEY_NUMBER) {
            // 将当前节点的父节点位于当前孩子索引前一个位置处的key和value插入到当前节点索引0位置处
            node.insertKey(parent.keys.get(index - 1), parent.values.get(index - 1), 0);
            // 如果不是叶子节点，则把左兄弟的最右孩子插入到当前节点索引0位置处
            if (!leftSibling.isLeaf) { // 当上一级的删除方法开始归的过程的时候，会出现兄弟节点不是叶子节点，所以要判断
                node.insertChild(leftSibling.removeRightMostChild(), 0);
            }
            // 当前节点的父节点的当前索引减一处改为左兄弟最右边的的key和value
            parent.keys.set(index - 1, leftSibling.removeRightMostKey());
            parent.values.set(index - 1, leftSibling.removeRightMostValue());
        }
        // 当前要处理的节点的右兄弟富余，则来一次左旋
        else if (rightSibling != null && rightSibling.keys.size() > MIN_KEY_NUMBER) {
            // 将当前节点的父节点位于当前孩子索引处的key和value插入到当前节点索引最后一个位置处
            node.insertKey(parent.keys.get(index), parent.values.get(index), node.keys.size());
            // 如果不是叶子节点，则把右兄弟的最左孩子插入到当前节点索引最后一个位置处
            if (!rightSibling.isLeaf) { // 当上一级的删除方法开始归的过程的时候，会出现兄弟节点不是叶子节点，所以要判断
                node.insertChild(rightSibling.removeLeftMostChild(), node.children.size());
            }
            // 当前节点的父节点的当前索引改为右兄弟最左边的的key和value
            parent.keys.set(index, rightSibling.removeLeftMostKey());
            parent.values.set(index, rightSibling.removeLeftMostValue());
        }
        // 当前要处理的节点的左右兄弟都不富余，则向左合并
        else {
            // 如果有左兄弟，则向左合并（包括当前节点和父节点的一个key）
            if (leftSibling != null){
                // 将当前节点与父节点断开父子关系
                parent.removeChild(index);
                // 将父节点的当前索引减一处的key和value插入到左兄弟的末尾
                leftSibling.insertKey(parent.keys.get(index - 1),parent.values.get(index - 1), leftSibling.keys.size());
                // 删除父节点的当前索引减一处的key
                parent.removeKey(index - 1);
                // 删除父节点的当前索引减一处的value
                parent.removeValue(index - 1);
                // 将当前节点的key、value、子树移动到左兄弟的key、value、子树末尾
                if (node != null) {
                    node.moveToTarget(leftSibling);
                }
            }
            // 如果没有左兄弟，则将右边的合并到当前节点（包括右兄弟的全部和父节点的一个key）
            else {
                // 将当前节点的兄弟节点与父节点断开父子关系
                parent.removeChild(index + 1);
                // 将父节点的当前索引处的key和value插入到当前节点的末尾
                node.insertKey(parent.keys.get(index), parent.values.get(index), node.keys.size());
                // 删除父节点的当前索引处的key
                parent.removeKey(index);
                // 删除父节点的当前索引处的value
                parent.removeValue(index);
                // 如果有右兄弟，则将右兄弟的key、value、子树移动到当前节点的key、value、子树末尾
                if (rightSibling != null) {
                    rightSibling.moveToTarget(node);
                }
            }
        }
    }

    @Override
    @SuppressWarnings("all")
    public String toString() {
        LinkedList<BNode<K, V>> queue = new LinkedList<>();
        queue.push(root);
        ArrayList<K> kList = new ArrayList<>();
        ArrayList<V> vList = new ArrayList<>();
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++){
                BNode<K, V> last = queue.poll();
                kList.addAll(last.keys);
                vList.addAll(last.values);
                if (!last.isLeaf){
                    for (BNode<K, V> child : last.children) {
                        queue.offer(child);
                    }
                }
            }
        }
        return "key = " + kList.toString()
                + "\r\n" +
               "value = "+ vList.toString();
    }
}
